{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Bulb Switcher II"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #bit-manipulation #depth-first-search #breadth-first-search #math"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #位运算 #深度优先搜索 #广度优先搜索 #数学"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: flipLights"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #灯泡开关 Ⅱ"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>房间中有 <code>n</code>&nbsp;只已经打开的灯泡，编号从 <code>1</code> 到 <code>n</code> 。墙上挂着 <strong>4 个开关</strong> 。</p>\n",
    "\n",
    "<p>这 4 个开关各自都具有不同的功能，其中：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li><strong>开关 1 ：</strong>反转当前所有灯的状态（即开变为关，关变为开）</li>\n",
    "\t<li><strong>开关 2 ：</strong>反转编号为偶数的灯的状态（即 <code>0, 2, 4, ...</code>）</li>\n",
    "\t<li><strong>开关 3 ：</strong>反转编号为奇数的灯的状态（即 <code>1, 3, ...</code>）</li>\n",
    "\t<li><strong>开关 4 ：</strong>反转编号为 <code>j = 3k + 1</code> 的灯的状态，其中 <code>k = 0, 1, 2, ...</code>（即 <code>1, 4, 7, 10, ...</code>）</li>\n",
    "</ul>\n",
    "\n",
    "<p>你必须 <strong>恰好</strong> 按压开关 <code>presses</code> 次。每次按压，你都需要从 4 个开关中选出一个来执行按压操作。</p>\n",
    "\n",
    "<p>给你两个整数 <code>n</code> 和 <code>presses</code> ，执行完所有按压之后，返回 <strong>不同可能状态</strong> 的数量。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 1, presses = 1\n",
    "<strong>输出：</strong>2\n",
    "<strong>解释：</strong>状态可以是：\n",
    "- 按压开关 1 ，[关]\n",
    "- 按压开关 2 ，[开]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 2, presses = 1\n",
    "<strong>输出：</strong>3\n",
    "<strong>解释：</strong>状态可以是：\n",
    "- 按压开关 1 ，[关, 关]\n",
    "- 按压开关 2 ，[开, 关]\n",
    "- 按压开关 3 ，[关, 开]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 3, presses = 1\n",
    "<strong>输出：</strong>4\n",
    "<strong>解释：</strong>状态可以是：\n",
    "- 按压开关 1 ，[关, 关, 关]\n",
    "- 按压开关 2 ，[关, 开, 关]\n",
    "- 按压开关 3 ，[开, 关, 开]\n",
    "- 按压开关 4 ，[关, 开, 开]\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= n &lt;= 1000</code></li>\n",
    "\t<li><code>0 &lt;= presses &lt;= 1000</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [bulb-switcher-ii](https://leetcode.cn/problems/bulb-switcher-ii/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [bulb-switcher-ii](https://leetcode.cn/problems/bulb-switcher-ii/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['1\\n1', '2\\n1', '3\\n1']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def flipLights(self, n: int, presses: int) -> int:\n",
    "        if 0==presses:\n",
    "            return 1\n",
    "        if n<=2:\n",
    "            return 2 if 1==n else (3 if presses==1 else 4)\n",
    "        return (4 if presses==1 else 7) if presses<=2 else 8"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def flipLights(self, n: int, presses: int) -> int:\n",
    "        return 1 if not presses else (2 if n == 1 else ((4 if presses == 1 else (7 if presses == 2 else 8)) if n > 2 else (3 if presses == 1 else 4)))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def flipLights(self, n: int, presses: int) -> int:\n",
    "        n = min(3, n)\n",
    "        presses = min(3, presses)\n",
    "        res = [[1,2,2,2],[1,3,4,4],[1,4,7,8]]\n",
    "        return res[n - 1][presses]\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def flipLights(self, n: int, presses: int) -> int:\n",
    "\n",
    "        if presses == 0:\n",
    "            return 1\n",
    "        # 特殊情况处理\n",
    "        if n == 1:\n",
    "            return 2\n",
    "        elif n == 2:\n",
    "            # 特殊情况\n",
    "            return 3 if presses == 1 else 4\n",
    "        else:\n",
    "            # n >= 3\n",
    "            return 4 if presses == 1 else (7 if presses == 2 else 8)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # @lru_cache(maxsize=int(1e4))\n",
    "    def dp(self, p, s):\n",
    "        if s == 1:\n",
    "            return 1\n",
    "        if p == 1:\n",
    "            return s\n",
    "        return self.dp(p - 1, s - 1) + self.dp(p, s - 1)\n",
    "    def flipLights(self, n: int, presses: int) -> int:\n",
    "        if presses == 0:\n",
    "            return 1\n",
    "        if n == 1:\n",
    "            return self.dp(presses, 2)\n",
    "        if n == 2:\n",
    "            return self.dp(presses, 3)\n",
    "        return self.dp(presses, 4)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def flipLights(self, n: int, presses: int) -> int:\n",
    "        if n >= 3:\n",
    "            if presses >= 3:\n",
    "                return 8\n",
    "            elif presses == 2:\n",
    "                return 7\n",
    "            elif presses == 1:\n",
    "                return 4\n",
    "            else:\n",
    "                return 1\n",
    "        elif n == 2:\n",
    "            if presses >= 2:\n",
    "                return 4\n",
    "            elif presses == 1:\n",
    "                return 3\n",
    "            else:\n",
    "                return 1\n",
    "        else:\n",
    "            if presses >= 1:\n",
    "                return 2\n",
    "            else:\n",
    "                return 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def flipLights(self, n: int, presses: int) -> int:\n",
    "        if presses==0:\n",
    "            return 1\n",
    "        if n==1:\n",
    "            return 2\n",
    "        elif n==2:\n",
    "            return 3 if presses==1 else 4\n",
    "        else:\n",
    "            return 4 if presses==1 else 7 if presses==2 else 8"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def flipLights(self, n: int, presses: int) -> int:\n",
    "        seen = set()\n",
    "        for i in range(2**4):\n",
    "            pressArr = [(i >> j) & 1 for j in range(4)]\n",
    "            if sum(pressArr) % 2 == presses % 2 and sum(pressArr) <= presses:\n",
    "                status = pressArr[0] ^ pressArr[2] ^ pressArr[3]\n",
    "                if n >= 2:\n",
    "                    status |= (pressArr[0] ^ pressArr[1]) << 1\n",
    "                if n >= 3:\n",
    "                    status |= (pressArr[0] ^ pressArr[2]) << 2\n",
    "                if n >= 4:\n",
    "                    status |= (pressArr[0] ^ pressArr[1] ^ pressArr[3]) << 3\n",
    "                seen.add(status)\n",
    "        return len(seen)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def flipLights(self, n: int, presses: int) -> int:\n",
    "    \n",
    "        if n == 0:\n",
    "            return 0 \n",
    "        if presses == 0:\n",
    "            return 1 \n",
    "\n",
    "        if n == 1:\n",
    "            return 2\n",
    "        if n == 2:\n",
    "            if presses == 1:\n",
    "                return 3 \n",
    "            else:\n",
    "                return 4\n",
    "        if n >= 3:\n",
    "            if presses == 1:\n",
    "                return 4 \n",
    "            elif presses == 2:\n",
    "                return 7 \n",
    "            else:\n",
    "                return 8 \n",
    "\n",
    "            \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def flipLights(self, n: int, presses: int) -> int:\n",
    "        if presses==0:\n",
    "            return 1\n",
    "        if n==1:\n",
    "            return 2\n",
    "        if n==2 and presses==1:\n",
    "            return 3 \n",
    "        if n==2 and presses>=2:\n",
    "            return 4\n",
    "        if n>=3 and presses==1:\n",
    "            return 4 \n",
    "        if n>=3 and presses==2:\n",
    "            return 7\n",
    "        if n>=3 and presses>=3:\n",
    "            return 8"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    @lru_cache(maxsize=int(1e4))\n",
    "    def dp(self, p, s):\n",
    "        if s == 1:\n",
    "            return 1\n",
    "        if p == 1:\n",
    "            return s\n",
    "        return self.dp(p - 1, s - 1) + self.dp(p, s - 1)\n",
    "    def flipLights(self, n: int, presses: int) -> int:\n",
    "        if presses == 0:\n",
    "            return 1\n",
    "        if n == 1:\n",
    "            return self.dp(presses, 2)\n",
    "        if n == 2:\n",
    "            return self.dp(presses, 3)\n",
    "        return self.dp(presses, 4)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def flipLights(self, n, m):\n",
    "        \"\"\"\n",
    "        :type n: int\n",
    "        :type m: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if m == 0:\n",
    "            return 1\n",
    "        if n >= 3:\n",
    "            return 4 if m == 1 else 7 if m == 2 else 8\n",
    "        if n == 2:\n",
    "            return 3 if m == 1 else 4\n",
    "        if n == 1:\n",
    "            return 2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def flipLights(self, n: int, presses: int) -> int:\n",
    "        if presses == 0:\n",
    "            return 1\n",
    "        if n == 1:\n",
    "            return 2\n",
    "        elif n == 2:\n",
    "            if presses==1:\n",
    "                return 3\n",
    "            else:\n",
    "                return 4\n",
    "        else:\n",
    "            if presses==1:\n",
    "                return 4\n",
    "            elif presses==2:\n",
    "                return 7\n",
    "            else:\n",
    "                return 8"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def flipLights(self, n: int, presses: int) -> int:\n",
    "        if presses == 0:\n",
    "            return 1\n",
    "        if n == 1:\n",
    "            return 2\n",
    "        if n == 2:\n",
    "            return 3 if presses == 1 else 4\n",
    "        if presses == 1:\n",
    "            return 4\n",
    "        if presses == 2:\n",
    "            return 7\n",
    "        return 8"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def flipLights(self, n: int, presses: int) -> int:\n",
    "        if presses == 0:\n",
    "            return 1\n",
    "        if n == 1:\n",
    "            return 2\n",
    "        if n == 2:\n",
    "            return 3 if presses == 1 else 4\n",
    "        if presses == 1:\n",
    "            return 4\n",
    "        return 7 if presses == 2 else 8\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def flipLights(self, n: int, presses: int) -> int:\n",
    "        # 注意：\n",
    "        # 1. 灯的状态的周期为 T=6，即1号灯泡状态和7号灯泡始终相同\n",
    "        # 2. 1-6号灯泡里，2号和6号、3号和5号的状态始终是一样的\n",
    "        # 1&2 -> 因此只需要判断1，2，3，4号灯泡的状态，就知道有多少种状态\n",
    "        # 3. 如果1号和3号状态相同，则按钮4被按了偶数次；反之则按了奇数次\n",
    "        # 4. 如果按钮4被按了偶数次，则2号和4号状态相同，反之状态不同\n",
    "        # 3&4 -> 因此可以从1，2，3号灯泡状态判断出四号状态，只需要观察前三盏灯\n",
    "        # 所有灯一开始都是亮着：111 (*) 1种\n",
    "        # 按一次：000，101，010，011 (**) 4种\n",
    "        # 按两次：111，000，101，010，100，110，001 (***) 7种\n",
    "        # 按三次：111，000，101，010，100，110，001，011 (****) 8种\n",
    "        if presses == 0: return 1\n",
    "        elif n == 1: return 2\n",
    "        elif n == 2:\n",
    "            if presses == 1: return 3\n",
    "            else: return 4\n",
    "        else:\n",
    "            if presses == 1: return 4\n",
    "            elif presses == 2: return 7\n",
    "            else: return 8\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def flipLights(self, n: int, presses: int) -> int:\n",
    "        if presses == 0:\n",
    "            return 1\n",
    "        if n > 2:\n",
    "            if presses == 1:\n",
    "                return 4\n",
    "            if presses == 2:\n",
    "                return comb(4, 2) + 1 # 4个操作里选两个的选法，加上空操作\n",
    "            if presses == 3:\n",
    "                return comb(4, 3) + 4 # 4个操作里选三个的选法，加上两个操作出空+选一个操作\n",
    "            if presses == 4:\n",
    "                return comb(4, 2) + 2 # 4个操作里选两个的选法加上两个操作出空，加上选出空操作以及四个都选\n",
    "            return comb(4, 2) + 2 # 奇数可以退化到3，偶数可以退化到4\n",
    "        elif n == 2:\n",
    "            if presses == 1:\n",
    "                return 3 \n",
    "            if presses == 2:\n",
    "                return comb(3, 2) + 1\n",
    "            if presses == 3:\n",
    "                return comb(3, 1) + 1\n",
    "            return 4 # 奇数可以退化到3，偶数可以退化到2\n",
    "        return 2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def flipLights(self, n: int, presses: int) -> int:\n",
    "        if presses == 0:\n",
    "            return 1\n",
    "        if n == 1:\n",
    "            return 2\n",
    "        elif n == 2:\n",
    "            return 3 if presses == 1 else 4\n",
    "        else:\n",
    "            if presses == 1:\n",
    "                return 4\n",
    "            if presses == 2:\n",
    "                return 7\n",
    "            else:\n",
    "                return 8"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def flipLights(self, n: int, presses: int) -> int:\n",
    "        if presses == 0: return 1\n",
    "        if n == 1: return 2\n",
    "        elif n == 2: return 3 if presses == 1 else 4\n",
    "        return 4 if presses == 1 else 7 if presses == 2 else 8"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def flipLights(self, n: int, presses: int) -> int:\n",
    "        if presses>0:\n",
    "            if n==1:\n",
    "                return 2\n",
    "            elif n==2:\n",
    "                if presses==1:\n",
    "                    return 3\n",
    "                else:\n",
    "                    return 4\n",
    "            else:\n",
    "                if presses==1:\n",
    "                    return 4\n",
    "                elif presses==2:\n",
    "                    return 7\n",
    "                else:\n",
    "                    return 8\n",
    "        if presses==0:\n",
    "            return 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def flipLights(self, n: int, k: int) -> int:\n",
    "        if k == 0:\n",
    "            return 1\n",
    "        if n == 1:\n",
    "            return 2\n",
    "        elif n == 2:\n",
    "            return 3 + (k != 1)\n",
    "        else:\n",
    "            return 4 if k == 1 else (7 if k == 2 else 8)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def flipLights(self, n: int, k: int) -> int:\n",
    "        if k == 0:\n",
    "            return 1\n",
    "        if n == 1:\n",
    "            return 2\n",
    "        elif n == 2:\n",
    "            return 3 if k == 1 else 4\n",
    "        else:\n",
    "            return 4 if k == 1 else 7 if k == 2 else 8"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def flipLights(self, n: int, presses: int) -> int:\n",
    "        if presses == 0:\n",
    "            return 1\n",
    "        if n == 1:\n",
    "            return 2\n",
    "        elif n == 2:\n",
    "            return 3 if presses == 1 else 4\n",
    "        else:\n",
    "            return 4 if presses == 1 else 7 if presses == 2 else 8"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def flipLights(self, n: int, presses: int) -> int:\n",
    "        if presses == 0:\n",
    "            return 1\n",
    "        if n == 1:\n",
    "            return 2\n",
    "        elif n == 2:\n",
    "            if presses == 1:\n",
    "                return 3\n",
    "            else:\n",
    "                return 4\n",
    "        else:\n",
    "            if presses == 1:\n",
    "                return 4\n",
    "            elif presses == 2:\n",
    "                return 7\n",
    "            else:\n",
    "                return 8\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def flipLights(self, n: int, presses: int) -> int:\n",
    "        if presses == 0:\n",
    "            return 1\n",
    "        if n == 1:\n",
    "            return 2\n",
    "        if n == 2:\n",
    "            if presses == 1:\n",
    "                return 3\n",
    "            return 4\n",
    "        if n >= 3:\n",
    "            if presses == 1:\n",
    "                return 4\n",
    "            elif presses == 2:\n",
    "                return 7\n",
    "            return 8"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def flipLights(self, n: int, presses: int) -> int:\n",
    "        if presses==0:\n",
    "            return 1\n",
    "        if n==1:\n",
    "            return 2 \n",
    "        if n==2:\n",
    "            if presses==1:\n",
    "                return 3\n",
    "            else:\n",
    "                return 4 \n",
    "        if presses==1:\n",
    "            return 4\n",
    "        elif presses==2:\n",
    "            return 7 \n",
    "        else:\n",
    "            return 8\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def flipLights(self, n: int, presses: int) -> int:\n",
    "        if presses == 0: return 1\n",
    "        if n == 1 and presses > 0: return 2\n",
    "        if n == 2 and presses == 1: return 3\n",
    "        if (n == 2 and presses >= 2) or (n >= 3 and presses == 1): return 4\n",
    "        if n >= 3 and presses == 2: return 7\n",
    "        return 8"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def flipLights(self, n: int, presses: int) -> int:\n",
    "        if n >= 6:\n",
    "            n = 6 + n % 6\n",
    "        mask1 = ((1 << n) - 1)\n",
    "        mask2 = 0\n",
    "        mask3 = 0\n",
    "        mask4 = 0\n",
    "        for i in range(0, n, 2):\n",
    "            mask2 |= (1 << i)\n",
    "        for i in range(1, n, 2):\n",
    "            mask3 |= (1 << (i))\n",
    "        for i in range(0, n, 3):\n",
    "            mask4 |= (1 << i)\n",
    "        masks = list(set([mask1, mask2, mask3, mask4]))\n",
    "        queue = set([0])\n",
    "        # d = set()\n",
    "        step = 0\n",
    "        while len(queue) > 0 and step < presses:\n",
    "            new_queue = set()\n",
    "            for now in queue:\n",
    "                for mask in masks:\n",
    "                    new_queue.add(mask ^ now)\n",
    "            if queue == new_queue:\n",
    "                break\n",
    "            queue = new_queue\n",
    "            step += 1\n",
    "        return len(queue)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def flipLights(self, n: int, presses: int) -> int:\n",
    "        if presses == 0:\n",
    "            return 1\n",
    "        if n == 1:\n",
    "            return 2\n",
    "        elif n == 2:\n",
    "            if presses==1:\n",
    "                return 3\n",
    "            else:\n",
    "                return 4\n",
    "        else:\n",
    "            if presses==1:\n",
    "                return 4\n",
    "            elif presses==2:\n",
    "                return 7\n",
    "            else:\n",
    "                return 8"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def flipLights(self, n: int, presses: int) -> int:\n",
    "        if presses == 0:\n",
    "            return 1\n",
    "        if n > 2:\n",
    "            if presses == 1:\n",
    "                return 4\n",
    "            if presses == 2:\n",
    "                return comb(4, 2) + 1 # 4个操作里选两个的选法，加上空操作\n",
    "            if presses == 3:\n",
    "                return comb(4, 3) + 4 # 4个操作里选三个的选法，加上两个操作出空+选一个操作\n",
    "            if presses == 4:\n",
    "                return comb(4, 2) + 2 # 4个操作里选两个的选法加上两个操作出空，加上选出空操作以及四个都选\n",
    "            return comb(4, 2) + 2 # 奇数可以退化到3，偶数可以退化到4\n",
    "        elif n == 2:\n",
    "            if presses == 1:\n",
    "                return 3 \n",
    "            if presses == 2:\n",
    "                return comb(3, 2) + 1\n",
    "            if presses == 3:\n",
    "                return comb(3, 1) + 1\n",
    "            return 4 # 奇数可以退化到3，偶数可以退化到2\n",
    "        return 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\tdef flipLights(self, n, presses):\n",
    "\t\tt, s = [x for x in range(5) if x <= presses and (presses - x) % 2 == 0], set()\n",
    "\t\tfor i in range(1 << 4):\n",
    "\t\t\tc, x = 0, i\n",
    "\t\t\twhile x > 0: c, x = c + 1, x & (x - 1)\n",
    "\t\t\tif c not in t: continue\n",
    "\t\t\ta = [1] * n\n",
    "\t\t\tif (i & (1 << 0)) != 0:\n",
    "\t\t\t\tfor j in range(n): a[j] ^= 1\n",
    "\t\t\tif (i & (1 << 1)) != 0:\n",
    "\t\t\t\tfor j in range(0, n, 2): a[j] ^= 1\n",
    "\t\t\tif (i & (1 << 2)) != 0:\n",
    "\t\t\t\tfor j in range(1, n, 2): a[j] ^= 1\n",
    "\t\t\tif (i & (1 << 3)) != 0:\n",
    "\t\t\t\tfor j in range(0, n, 3): a[j] ^= 1\n",
    "\t\t\ts.add(tuple(a))\n",
    "\t\treturn len(s)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def flipLights(self, n: int, presses: int) -> int:\n",
    "        seen = set()\n",
    "        for i in range(2**4):\n",
    "            pressArr = [(i >> j) & 1 for j in range(4)]\n",
    "            if sum(pressArr) % 2 == presses % 2 and sum(pressArr) <= presses:\n",
    "                status = pressArr[0] ^ pressArr[2] ^ pressArr[3]\n",
    "                if n >= 2:\n",
    "                    status |= (pressArr[0] ^ pressArr[1]) << 1\n",
    "                if n >= 3:\n",
    "                    status |= (pressArr[0] ^ pressArr[2]) << 2\n",
    "                if n >= 4:\n",
    "                    status |= (pressArr[0] ^ pressArr[1] ^ pressArr[3]) << 3\n",
    "                seen.add(status)\n",
    "        return len(seen)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def flipLights(self, n: int, presses: int) -> int:\n",
    "        if presses == 0:\n",
    "            return 1\n",
    "        if n == 1:\n",
    "            return 2\n",
    "        elif n == 2:\n",
    "            return 3 if presses ==1 else 4\n",
    "        else:return 4 if presses==1 else 7 if presses==2 else 8\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def flipLights(self, n: int, presses: int) -> int:\n",
    "        # If 0 presses, only one state is possible.\n",
    "        if presses == 0:\n",
    "            return 1\n",
    "\n",
    "        # For n=1\n",
    "        if n == 1:\n",
    "            return 2\n",
    "\n",
    "        # For n=2\n",
    "        if n == 2:\n",
    "            return 3 if presses == 1 else 4  # Fixing this line\n",
    "\n",
    "        # For n>=3\n",
    "        if presses == 1:\n",
    "            return 4\n",
    "        if presses == 2:\n",
    "            return 7\n",
    "        return 8  # for presses >= 3\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def flipLights(self, n: int, presses: int) -> int:\n",
    "        # 注意：\n",
    "        # 1. 灯的状态的周期为 T=6，即1号灯泡状态和7号灯泡始终相同\n",
    "        # 2. 1-6号灯泡里，2号和6号、3号和5号的状态始终是一样的\n",
    "        # 1&2 -> 因此只需要判断1，2，3，4号灯泡的状态，就知道有多少种状态\n",
    "        # 3. 如果1号和3号状态相同，则按钮4被按了偶数次；反之则按了奇数次\n",
    "        # 4. 如果按钮4被按了偶数次，则2号和4号状态相同，反之状态不同\n",
    "        # 3&4 -> 因此可以从1，2，3号灯泡状态判断出四号状态，只需要观察前三盏灯\n",
    "        # 所有灯一开始都是亮着：111 (*) 1种\n",
    "        # 按一次：000，101，010，011 (**) 4种\n",
    "        # 按两次：111，000，101，010，100，110，001 (***) 7种\n",
    "        # 按三次：111，000，101，010，100，110，001，011 (****) 8种\n",
    "        if presses == 0: return 1\n",
    "        elif n == 1: return 2\n",
    "        elif n == 2:\n",
    "            if presses == 1: return 3\n",
    "            else: return 4\n",
    "        elif n == 3: \n",
    "            if presses == 1: return 4\n",
    "            elif presses == 2: return 7\n",
    "            else: return 8\n",
    "        else:\n",
    "            if presses == 1: return 4\n",
    "            elif presses == 2: return 7\n",
    "            else: return 8\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def flipLights(self, n: int, presses: int) -> int:\n",
    "        if presses == 0:\n",
    "            return 1\n",
    "        if n > 2:\n",
    "            if presses == 1:\n",
    "                return 4\n",
    "            if presses == 2:\n",
    "                return comb(4, 2) + 1 # 4个操作里选两个的选法，加上空操作\n",
    "            if presses == 3:\n",
    "                return comb(4, 3) + 4 # 4个操作里选三个的选法，加上两个操作出空+选一个操作\n",
    "            if presses == 4:\n",
    "                return comb(4, 2) + 2 # 4个操作里选两个的选法加上两个操作出空，加上选出空操作以及四个都选\n",
    "            return comb(4, 2) + 2 # 奇数可以退化到3，偶数可以退化到4\n",
    "        elif n == 2:\n",
    "            if presses == 1:\n",
    "                return 3 \n",
    "            if presses == 2:\n",
    "                return comb(3, 2) + 1\n",
    "            if presses == 3:\n",
    "                return comb(3, 1) + 1\n",
    "            return 4 # 奇数可以退化到3，偶数可以退化到2\n",
    "        return 2\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def flipLights(self, n: int, presses: int) -> int:\r\n",
    "        seen=set()\r\n",
    "        for i in range(2**4):\r\n",
    "            pressArray=[(i>>j)&1 for j in range(4)]\r\n",
    "            if sum(pressArray)%2 == presses%2 and sum(pressArray)<=presses:\r\n",
    "                status = pressArray[0] ^ pressArray[2] ^ pressArray[3]\r\n",
    "                if n >= 2:\r\n",
    "                    status |= (pressArray[0] ^ pressArray[1]) << 1\r\n",
    "                if n >= 3:\r\n",
    "                    status |= (pressArray[0] ^ pressArray[2]) << 2\r\n",
    "                if n >= 4:\r\n",
    "                    status |= (pressArray[0] ^ pressArray[1] ^ pressArray[3]) << 3\r\n",
    "                seen.add(status)\r\n",
    "        return len(seen)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def flipLights(self, n: int, presses: int) -> int:\n",
    "        if presses == 0:\n",
    "            return 1\n",
    "        \n",
    "        if n == 1:\n",
    "            return 2\n",
    "        elif n == 2:\n",
    "            return 3 if presses == 1 else 4\n",
    "        else:\n",
    "            if presses == 1:\n",
    "                return 4\n",
    "            elif presses == 2:\n",
    "                return 7\n",
    "            else:\n",
    "                return 8"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def flipLights(self, n: int, presses: int) -> int:\n",
    "        \n",
    "        n = min(n ,4)\n",
    "        dq = deque(['1'*n])\n",
    "\n",
    "        for i in range(presses):\n",
    "            states = set()\n",
    "            for j in range(len(dq)):\n",
    "                s = dq.pop()\n",
    "                for k in range(1,5):\n",
    "                    next_state = self.flip(s, k)\n",
    "                    if next_state not in states:\n",
    "                        states.add(next_state)\n",
    "                        dq.appendleft(next_state)\n",
    "\n",
    "        return len(dq)\n",
    "\n",
    "\n",
    "    def flip(self,string, k):\n",
    "        flip_string = ''\n",
    "        for i in range(len(string)):\n",
    "            if {\n",
    "                1: lambda x : True,\n",
    "                2: lambda x : x%2 == 0,\n",
    "                3: lambda x : x%2 == 1,\n",
    "                4: lambda x : x%3 == 1\n",
    "                }[k](i+1):\n",
    "                flip_string += str(1-int(string[i]))\n",
    "            else:\n",
    "                flip_string += string[i]\n",
    "        return flip_string\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def flipLights(self, n: int, presses: int) -> int:\n",
    "        if presses==0:\n",
    "            return 1\n",
    "        if n==1:\n",
    "            return 2\n",
    "        if n==2:\n",
    "            if presses==1:\n",
    "                return 3\n",
    "            else:\n",
    "                return 4\n",
    "        if presses==1:\n",
    "            return 4\n",
    "        if presses==2:\n",
    "            return 7\n",
    "        else:\n",
    "            return 8"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def flipLights(self, n: int, k: int) -> int:\n",
    "        if k == 0:\n",
    "            return 1\n",
    "        if n == 1:\n",
    "            return 2\n",
    "        elif n == 2:\n",
    "            return 3 + (k != 1)\n",
    "        else:\n",
    "            return 4 if k == 1 else (7 if k == 2 else 8)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def flipLights(self, n: int, presses: int) -> int:\n",
    "        seen = set()\n",
    "        for i in range(2**4):\n",
    "            pressArr = [(i >> j) & 1 for j in range(4)]\n",
    "            if sum(pressArr) % 2 == presses % 2 and sum(pressArr) <= presses:\n",
    "                status = pressArr[0] ^ pressArr[2] ^ pressArr[3]\n",
    "                if n >= 2:\n",
    "                    status |= (pressArr[0] ^ pressArr[1]) << 1\n",
    "                if n >= 3:\n",
    "                    status |= (pressArr[0] ^ pressArr[2]) << 2\n",
    "                if n >= 4:\n",
    "                    status |= (pressArr[0] ^ pressArr[1] ^ pressArr[3]) << 3\n",
    "                seen.add(status)\n",
    "        return len(seen)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def flipLights(self, n: int, presses: int) -> int:\n",
    "        if presses == 0:\n",
    "            return 1\n",
    "        if n == 1:\n",
    "            return 2\n",
    "        elif n == 2:\n",
    "            return 3 if presses == 1 else 4\n",
    "        else:\n",
    "            return 4 if presses == 1 else 7 if presses == 2 else 8"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def flipLights(self, n: int, presses: int) -> int:\r\n",
    "        if presses <= 0: return 1\r\n",
    "        # 0个灯泡\r\n",
    "        if n == 0: return 1\r\n",
    "        # 1个灯泡，要么开，要么关\r\n",
    "        if n == 1: return 2\r\n",
    "        # 2个灯泡，要么全开，要么全关，要么奇数开，要么偶数开\r\n",
    "        if n == 2: return 3 if presses == 1 else 4\r\n",
    "        if n >= 3:\r\n",
    "            if presses == 1:\r\n",
    "                return 4\r\n",
    "            elif presses == 2:\r\n",
    "                return 7\r\n",
    "            else:\r\n",
    "                return 8"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def flipLights(self, n: int, presses: int) -> int:\n",
    "        seen = set()\n",
    "        for i in range(2**4):\n",
    "            pressArr = [(i >> j) & 1 for j in range(4)]\n",
    "            if sum(pressArr) % 2 == presses % 2 and sum(pressArr) <= presses:\n",
    "                status = pressArr[0] ^ pressArr[2] ^ pressArr[3]\n",
    "                if n >= 2:\n",
    "                    status |= (pressArr[0] ^ pressArr[1]) << 1\n",
    "                if n >= 3:\n",
    "                    status |= (pressArr[0] ^ pressArr[2]) << 2\n",
    "                if n >= 4:\n",
    "                    status |= (pressArr[0] ^ pressArr[1] ^ pressArr[3]) << 3\n",
    "                seen.add(status)\n",
    "        return len(seen)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def flipLights(self, n: int, presses: int) -> int:\n",
    "        n = min(n, 16) \n",
    "        vis = {0}\n",
    "        Q = deque([(0, 0)])\n",
    "        while Q:\n",
    "            d, x = Q.popleft() \n",
    "            if d >= presses:\n",
    "                continue\n",
    "            nx1,nx2,nx3 = x,x,x\n",
    "            for i in range(n):\n",
    "                if (i+1)%2 == 0:\n",
    "                    nx1 ^= 1 << i \n",
    "                if (i+1)%2 == 1:\n",
    "                    nx2 ^= 1 << i \n",
    "                if (i+1)%3 == 1:\n",
    "                    nx3 ^= 1 << i \n",
    "\n",
    "            if nx1 not in vis:\n",
    "                vis.add(nx1) \n",
    "                Q.append((d+1, nx1)) \n",
    "            if nx2 not in vis:\n",
    "                vis.add(nx2)\n",
    "                Q.append((d+1, nx2)) \n",
    "            if nx3 not in vis:\n",
    "                vis.add(nx3)\n",
    "                Q.append((d+1, nx3)) \n",
    "        return len(vis) \n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def flipLights(self, n: int, presses: int) -> int:\n",
    "        #同个开关连续按两次 等于没按\n",
    "        #1，4，7，10，13，16，19，22       1+3k\n",
    "        #1，3，7，9，11，13，15，17，。。。 1+2k\n",
    "        #0，2，4，6，8，10                 2k\n",
    "        #1,2,3,4,...                       k\n",
    "        \n",
    "        # 【1】 【2】 【3】 【4】 【1，2】，【1，3】，【1，4】，\n",
    "        # 琼剧\n",
    "\n",
    "        if presses == 0:\n",
    "            return 1\n",
    "        if n > 2:\n",
    "            if presses == 1:\n",
    "                return 4\n",
    "            if presses == 2:\n",
    "                return comb(4, 2) + 1 # 4个操作里选两个的选法，加上空操作\n",
    "            if presses == 3:\n",
    "                return comb(4, 3) + 4 # 4个操作里选三个的选法，加上两个操作出空+选一个操作\n",
    "            if presses == 4:\n",
    "                return comb(4, 2) + 2 # 4个操作里选两个的选法加上两个操作出空，加上选出空操作以及四个都选\n",
    "            return comb(4, 2) + 2 # 奇数可以退化到3，偶数可以退化到4\n",
    "        elif n == 2:\n",
    "            if presses == 1:\n",
    "                return 3 \n",
    "            if presses == 2:\n",
    "                return comb(3, 2) + 1\n",
    "            if presses == 3:\n",
    "                return comb(3, 1) + 1\n",
    "            return 4 # 奇数可以退化到3，偶数可以退化到2\n",
    "        return 2\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
